An ad-hoc network has been known as a type of a network. The ad-hoc network is a self-configured network which links by wireless communications. The ad-hoc network is configured by a plurality of devices having a communication function. A device having the communication function in the ad-hoc network is referred to as a node.
Each node in the ad-hoc network transmits or receives a packet with a multi-hop communication. The multi-hop communication is a technology that enables nodes, which are not present in their counterparts' service areas, to communicate with each other through a different node being present in the service area of each node. Note that a path to transfer a packet from a start point to an end point by the multi-hop communication is referred to as a transfer path. A transfer path is formed by a plurality of nodes being present from the start point to the end point.
For example, a meter-reading system has been known as a sensor network system of an ad-hoc type. A node capable of wireless communications is incorporated into a wattmeter of each household, and this meter-reading system gathers consumed electric energy and the like of each household, by way of the ad-hoc network. In this meter-reading system, packets containing information on consumed electric energy of each household which has been detected by each wattmeter are transferred from each node with which a wattmeter of each household is provided to a system of a power company.
From a standpoint of security, it is desirable that data in a packet is encrypted. For example, it is desirable that a data transmission source transmits data to a transmission destination after encrypting the data using a key for data encryption.
For example, a common key encryption method has been known as data encryption. In the common key encryption method, a data transmission source and a data transmission destination share a key for data encryption. To share this key, a conventional technology using Pairwise Key which is distributed in advance to each node has been known.
In this conventional technology, an ID (x, y) is assigned in advance to each node in a sensor network, and a plurality of Pairwise Keys corresponding to IDs are distributed. Then, using a Pairwise Key to be shared only between two nodes, the data transmission source and the data receipt destination share the key for data encryption.
As a conventional technology, Haowen Chan, Adrian Perrig, “PIKE: Peer Intermediaries for Key Establishment in Sensor Networks” (IEEE, IEEE INFOCOM 2005, pp. 524-535) has been known, for example.
In the conventional sensor network, m-squared nodes are first virtually arranged in a matrix of m rows by m columns. Then, an ID (i, j) containing two elements of a row and a column is assigned to each node. Note that a key for encryption of data in a packet is hereinafter referred to as a common key. In addition, a key which is used to share a common key and distributed in advance to each node is hereinafter referred to as a pre-shared key.
FIG. 1 is a view for illustrating a method for distributing a pre-shared key in the conventional sensor network. In FIG. 1, it is assumed that a total of nine nodes are arranged in a matrix of three rows by three columns and an ID is assigned to each node. For example, a node A is assigned an ID of (0, 0) and a node B an ID of (0, 1).
Then, a plurality of pre-shared keys are distributed to each node. The pre-shared key is a key shared by one node and another node having either row or column which is common to the one node.
For example, the node A (0, 0) has a pre-shared key AB with the node B (0, 1). The node A (0, 0) also has a pre-shared key AC with a node C (0, 2). In addition, the node A (0, 0) has a pre-shared key AD with a node D (1, 0). The node A (0, 0) also has a pre-shared key AG with a node G (2, 0). Note that each pre-shared key is a key which is shared only between two nodes and differs from the other pre-shared keys.
When the sensor network including nine nodes is constructed, as illustrated in FIG. 1, four pre-shared keys are distributed in advance to each node.
Since the node A (0, 0) shares the pre-shared key AB with the node B (0, 1), the node A (0, 0) may use the pre-shared key AB to share a common key to be used in encrypted communications with the node B (0, 1). On the one hand, the pre-shared key which the node A (0, 0) has differs from a pre-shared key which a node I (2, 2) has. Thus, the node A (0, 0) uses in the encrypted communications a node which shares a pre-shared key with the node A (0, 0) and which shares a pre-shared key with the node I (2, 2). In the example of FIG. 1, the node A (0, 0) uses the node C (0, 2) or the node G (2, 0) to share a common key used in the encrypted communications with the node C (0, 2).
Now, a case in which a new node is added to the ad-hoc network such as a sensor network is described. When a new node is added in a conventional sensor network, not only is an ID assigned to the new node, but also setting of a pre-shared key to be shared with another node for which either row or column is equal is requested. In addition, a pre-shared key to be shared with the new node is desirable to be distributed to nodes, which are already operating in the sensor network.
For example, suppose that an ID (0, 3) is assigned to a node J when the node J is added to the sensor network including the node A (0, 0) to node I (2, 2) in FIG. 1. Here, a pre-shared key uniquely shared between the node J (0, 3) and the node A (0, 0), a pre-shared key uniquely shared between the node J (0, 3) and the node B (0, 1), and a pre-shared key uniquely shared between the node J (0, 3) and the node C (0, 2) are distributed to the node J (0, 3). In addition, the unique pre-shared keys are desirable to be assigned respectively to the node A (0, 0), the node B (0, 1), and the node C (0, 2) which are already operating.